package com.aurora.leetcode.answer;

import com.aurora.leetcode.util.MyUtils;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;

/**
 * @author : Aurora
 * @date : 2024/5/30 15:01
 * @description
 * <p>28. 找出字符串中第一个匹配项的下标</p>
 * <p>给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项</p>
 * <p>的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回  -1 。</p>
 * <p>示例 1：</p>
 * <p>输入：haystack = "sadbutsad", needle = "sad"</p>
 * <p>输出：0</p>
 * <p>解释："sad" 在下标 0 和 6 处匹配。</p>
 * <p>第一个匹配项的下标是 0 ，所以返回 0 。</p>
 * <p>示例 2：</p>
 * <p>输入：haystack = "leetcode", needle = "leeto"</p>
 * <p>输出：-1</p>
 * <p>解释："leeto" 没有在 "leetcode" 中出现，所以返回 -1 。</p>

 */
public class StrStr_28 {
    public int strStr(String haystack, String needle) {
        //方法一：双层for循环
        if(haystack.length() < needle.length()) return -1;
        for(int i=0; i<=haystack.length()-needle.length(); ++i){
            int j = 0;
            for( j=0; j<needle.length(); ++j){
                if(needle.charAt(j) != haystack.charAt(i+j)) break;
            }
            if(j == needle.length()) return i;
        }
        return -1;
    }
    //方法二：KMP算法
    public int strStr2(String haystack, String needle) {
        //生成部分匹配表
        int[] computedPartialTab = computePartialTab(needle);
        int i=0, j=0;
        char[] textArr = haystack.toCharArray();
        char[] pattern = needle.toCharArray();
        while(i < haystack.length()){
            if(textArr[i] == pattern[j]){
                i ++;
                j ++;
            }
            if(j == needle.length()){
                return i - j;
            }else if(i < haystack.length() && textArr[i] != pattern[j]){
                if(j != 0){
                    j = computedPartialTab[j - 1];
                }else{
                    i++;
                }
            }
        }
        return -1;
    }

    private int[] computePartialTab(String needle) {
        int length = 0,i=1;
        char[] charArray = needle.toCharArray();
        int[] matchingTab = new int[needle.length()];
        while(i < needle.length()){
            if(charArray[length] == charArray[i]){
                length ++;
                matchingTab[i] = length;
                i++;
            }else if(length != 0){
                length = matchingTab[length - 1];
            }else{
                matchingTab[i] = 0;
                i++;
            }
        }
        return matchingTab;
    }

    public static void main(String[] args) {
        StrStr_28 obj = new StrStr_28();
//        System.out.println(obj.strStr("saabutsad", "sad"));
//        System.out.println(obj.strStr("aaa", "aab"));
        System.out.println(obj.strStr2("mississippi", "issip"));
        MyUtils.printArray(obj.computePartialTab("abeabf"));

    }
}
